#pragma once

template<class K>
struct BSNode
{
	K _key;
	BSNode<K>* _left;
	BSNode<K>* _right;

	BSNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};

template<class K>
class BSTree
{
	typedef BSNode<K> Node;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* perent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				perent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				perent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (key > perent->_key)
		{
			perent->_right = cur;
		}
		else
		{
			perent->_left = cur;
		}
		
		return true;
	}

private:
	Node* _root = nullptr;
};